package leetcode.list;

/**
 * Created by zxc on 2018/10/3.
 * 合并两条已排序链表
 */
public class MergeSortedList {
    static class ListNode {
        int val;
        ListNode next;
        ListNode(int x) {
            val = x;
        }
    }

    /*合并两条已排序链表*/
    private static ListNode mergeTwoSortedListA(ListNode headA, ListNode headB) {
        ListNode tempHead = new ListNode(0);
        ListNode tempP = tempHead;
        while (headA != null && headB != null) {
            if (headA.val < headB.val) {
                tempP.next = headA;
                headA = headA.next;
            }else {
                tempP.next = headB;
                headB = headB.next;
            }
            tempP = tempP.next;
        }
        if (headA != null) {
            tempP.next = headA;
        }
        if (headB != null) {
            tempP.next = headB;
        }
        return tempHead.next;
    }

    public static void main(String[] args) {
        ListNode node1 = new ListNode(1);
        ListNode node2 = new ListNode(2);
        ListNode node3 = new ListNode(3);

        ListNode node4 = new ListNode(4);
        ListNode node5 = new ListNode(5);

        ListNode node6 = new ListNode(6);
        ListNode node7 = new ListNode(7);

        node1.next=node2;
        node2.next=node3;
        node3.next=node6;
        node6.next=node7;
        node7.next=null;

        node4.next=node5;
        node5.next=null;

        ListNode  headA = node1;
        ListNode  headB = node4;

        System.out.println("Before find:");
        System.out.print("headA:");
        while (headA!=null){
            System.out.print(headA.val+">");
            headA = headA.next;
        }
        System.out.println("end");
        System.out.print("headB:");
        while (headB!=null){
            System.out.print(headB.val+">");
            headB = headB.next;
        }
        System.out.println("end");

        /*链表合并*/
        ListNode newHead = mergeTwoSortedListA(node1, node4);

        if(newHead != null) {
            System.out.println("链表合并：");
            while (newHead!=null){
                System.out.print(newHead.val+">");
                newHead = newHead.next;
            }
        }else{
            System.out.println("未合并" );
        }

        System.out.println("end");
    }
}
